# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        def merge(head1, head2):
            newHead = ListNode(None)
            cur = newHead
            while head1 and head2:
                if head1.val<head2.val:
                    cur.next = head1
                    head1 = head1.next
                    cur = cur.next
                    cur.next = None
                else:
                    cur.next = head2
                    head2 = head2.next
                    cur = cur.next
                    cur.next = None
            while head1:
                cur.next = head1
                head1 = head1.next
                cur = cur.next
                cur.next = None
            while head2:
                cur.next = head2
                head2 = head2.next
                cur = cur.next
                cur.next = None
            return newHead.next

        while len(lists)>1:
            tmp = []
            for i in range(len(lists)//2):
                tmp.append(merge(lists[i*2], lists[i*2+1]))
            if len(lists)%2==1:
                tmp.append(lists[-1])
            lists = tmp
        
        return lists[0] if len(lists)==1 else None